package com.fun.sort;

import java.util.Arrays;

/**
 * Created by han.yuan
 * 2018/4/8
 * 各种排序算法集合
 */
public class CrazySort {
    public static void main(String[] args){
        int a[]={1,4,3,2,5,6,10,9,33,12,43,54,76,86,13,44,56,99,61,333,564,644,23};
        System.out.println("原始数据："+Arrays.toString(a));
        long start=System.currentTimeMillis();
        //insertSort(a);
        //selectSort(a);
        //bubbleSort(a);
        quickSort(a,0,a.length-1);
        System.out.println("排序用时："+(System.currentTimeMillis()-start));
        System.out.println("排序后的数据："+Arrays.toString(a));

    }

    /**
     * 插入排序
     * @param a int数组
     *  在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，
     *  现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
     */
    public static void insertSort(int[] a){
        int length=a.length;
        int number;
        for(int i=1;i<length;i++){
            number=a[i];
            int j=i-1;
            while (j>0&&a[j]>number){
                a[j+1]=a[j];
                j--;
            }
            a[j+1]=number;
        }
    }

    /**
     * 希尔排序
     * @param a int数组
     * 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
     * 将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。
     * 再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。
     * 重复第二步，直到k=1执行简单插入排序。
     * 代码思路：
     * 首先确定分的组数。
     * 然后对组中元素进行插入排序。
     * 然后将length/2，重复1,2步，直到length=0为止。
     */
    public static void sheelSort(int[] a){
        int length=a.length;
        while(length!=0){
            length=length/2;
            for(int i=0;i<length;i++){ //分组
                for(int j=i+length;j<a.length;j+=length){ //元素从第二个开始
                    int k=j-length; //k为有序序列最后一位的位数
                    int temp=a[j];
                    while (k>0&&a[k]>temp){
                        a[k+length]=a[k];
                        k-=length;
                    }
                    a[k+length]=temp;

                }
            }
        }
    }

    /**
     * 简单选择排序
     * @param a int数组
     *  遍历整个序列，将最小的数放在最前面。
     *  遍历剩下的序列，将最小的数放在最前面。
     */
    public static void selectSort(int[] a){
       int length=a.length;
        for(int i=0;i<length;i++){
            int temp=a[i];
            int position=i;
            for(int j=i+1;j<length;j++){
                if(a[j]<temp){
                    temp=a[j];
                    position=j;
                }
            }
            if(position!=i){
                a[position]=a[i];
                a[i]=temp;
            }
        }
    }

    /**
     * 冒泡排序
     * 将序列中所有元素两两比较，将最大的放在最后面。
     * 将剩余序列中所有元素两两比较，将最大的放在最后面
     */
    public static void bubbleSort(int[] a){
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a.length-i-1;j++){
                if(a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;

                }
            }
        }
    }

    /**
     * 快速排序
     * 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
     * 递归的将p左边和右边的数都按照第一步进行，直到不能递归
     */
    public static void quickSort(int[] a,int left,int right){
        if(left>=right){
            //System.out.println("轮完一波");
            return;
        }
        //以最左边的为基数
        int i=left;
        int j=right;
        int key=a[left];
        /**
         * 控制在当前组内寻找一遍
         */
        while (i<j){
            //查找右边比key小的数字的下标
            while(i<j&&a[j]>key){
                j--;
            }
            //找到之后基数跟小值替换
            a[i]=a[j];
            //查找左边比key大的数字的下标
            while(i<j&&a[i]<key){
                i++;
            }
            //找到之后基数跟大的替换
            a[j]=a[i];
        }
        a[i]=key;
        quickSort(a,left,i-1);
        quickSort(a,i+1,right);
    }



}
